import sys
import copy
import math
from inspect import stack


class Solution:
    def isValid(self, s):
        stack = []
        map = {
            "{": "}",
            "[": "]",
            "(": ")"
        }

        for x in s:
            if x in map:
                stack.append(map[x])
            else:
                if len(stack) != 0:
                    top_element = stack.pop()
                    if x != top_element:
                        return False
                    else:
                        continue
                else:
                    return False

        return len(stack) == 0

    # """
    #
    # """
    def removeDuplicates(self, nums):
        if nums:
            slow = 0
            for fast in range(1, len(nums)):
                if nums[fast] != nums[slow]:
                    slow += 1
                    nums[slow] = nums[fast]
            return slow + 1
        else:
            return 0

    def maxSubArray(self, nums):
        n = len(nums)
        maxSum = -sys.maxsize
        sum = 0
        for i in range(n):
            sum = 0
            for j in range(i, n):
                sum += nums[j]
                maxSum = max(maxSum, sum)

        return maxSum

    def maxSubArray1(self, nums):
        n = len(nums)
        maxSum = nums[0]
        minSum = sum = 0
        for i in range(n):
            sum += nums[i]
            maxSum = max(maxSum, sum - minSum)
            minSum = min(minSum, sum)

        return maxSum

    def maxSuArray2(self, nums):
        return self.helper(nums, 0, len(nums) - 1)

    def helper(self, nums, l, r):
        if l > r:
            return sys.maxsize

        mid = (l + r) / 2
        left = self.helper(nums, l, mid - 1)
        right = self.helper(nums, mid + 1, r)
        left_suffix_max_sum = right_suffix_max_sum = 0
        sum = 0
        for i in reversed(range(l, mid)):
            sum += nums[i]
            left_suffix_max_sum = max(left_suffix_max_sum, sum)

        sum = 0
        for i in range(mid + 1, r + 1):
            sum += nums[i]
            right_suffix_max_sum = max(right_suffix_max_sum, sum)

        cross_max_sum = left_suffix_max_sum + right_suffix_max_sum + nums[mid]

        return max(cross_max_sum, left, right)

    def maxSubArray3(self, nums):
        n = len(nums)
        max_sum_ending_cur_index = max_sum = nums[0]
        for i in range(1, n):
            max_sum_ending_cur_index = max(max_sum_ending_cur_index + nums[i], nums[i])
            max_sum = max(max_sum_ending_cur_index, max_sum)

        return max_sum

    def merge(self, nums1, m, nums2, n):
        while m > 0 and n > 0:
            if nums1[m - 1] <= nums2[n - 1]:
                nums1[m + n - 1] = nums2[n - 1]
                n -= 1
            else:
                nums1[m + n - 1] = nums1[m - 1]
                m -= 1

        if n > 0:
            nums1[:n] = nums2[:n]

    def maxProfit(self, prices):
        if not prices: return 0

        min_price = sys.maxsize
        max_profic = 0

        for price in prices:
            if price < min_price:
                min_price = price
            elif max_profic < price - min_price:
                max_profic = price - min_price

        return max_profic

    def maxMulProfit(self, prices):
        gains = []
        for i in range(1, len(prices)):
            if prices[i] - prices[i - 1] > 0:
                gains.append(prices[i] - prices[i - 1])

        return sum(gains)

    def isPalindrome(self, s):
        left, right = 0, len(s) - 1
        while left < right:
            if not s[left].isalnum():
                left += 1
                continue
            if not s[right].isalnum():
                right -= 1
                continue
            if s[left].lower() == s[right].lower():
                left += 1
                right -= 1
            else:
                break

        return right <= left

    def isPalindrome2(self, s):
        s = ''.join(i for i in s if i.isalnum()).lower()
        return s == s[::-1]

    def singleNumber(self, nums):
        single_number = 0
        for num in nums:
            single_number ^= num

        return single_number

    def twoSum(self, nums, target):
        visited = {}
        for index, number in enumerate(nums):
            if target - number in visited:
                return [visited[target - number], index + 1]
            else:
                visited[number] = index + 1

    def twoSum2(self, nums, target):
        left, right = 0, len(nums) - 1
        while left < right:
            if nums[left] + nums[right] < target:
                left += 1
            if nums[left] + nums[right] > target:
                right -= 1
            if nums[left] + nums[right] == target:
                return [left + 1, right + 1]

    def trailingZeros(self, n):
        count = 0
        while n >= 5:
            n = n // 5
            count += n
        return count

    def trailingZeros2(self, n):
        if n == 0: return 0
        return n // 5 + self.trailingZeros2(n // 5)

    def jiechen(self, n):
        sum = 1
        for i in range(1, n):
            sum *= (i + 1)
        return sum

    def majorityElement(self, nums):
        count, majority = 1, nums[0]
        for num in nums[1:]:
            if count == 0:
                majority = num
            if majority == num:
                count += 1
            else:
                count -= 1

        return majority

    def reverseBits(self, n):
        result = 0
        for i in range(32):
            result = (result << 1) + (n & 1)
            n >>= 1
        return result

    def hanmingWeight(self, n):
        count = 0
        while n:
            n &= n - 1
            print ("hahah", n)
            count += 1

        return count

    def rob(self, nums):
        if not nums:
            return 0
        n = len(nums)

        if n == 1:
            return nums[0]
        else:
            prev = nums[0]
            cur = max(prev, nums[1])
            for i in range(2, n):
                cur, prev = max(prev + nums[i], cur), cur

        return cur

    def containsNearByDuplicate(self, nums, k):
        d = {}
        for index, num in enumerate(nums):
            if num in d and index - d[num] <= k:
                return True
            d[num] = index

        return False

    def isUgly(self, num):
        if num <= 0:
            return False

        for i in (2, 3, 5):
            while num % i == 0:
                num /= i

        return num == 1

    def moveZeros(self, nums):
        slow = fast = 0

        while fast < len(nums):
            if nums[fast] != 0:
                nums[fast], nums[slow] = nums[slow], nums[fast]
                slow += 1
            fast += 1

    def intersection(self, nums1, nums2):
        visited, result = {}, []
        for num in nums1:
            visited[num] = num

        for num in nums2:
            if num in visited:
                result.append(num)
                visited.pop(num)

        return result

    def intersection2(self, nums1, nums2):
        return set(nums1) & set(nums2)

    def getsum(self, a, b):
        if a == 0: return b
        if b == 0: return a

        return self.getsum(a ^ b, (a & b) << 1)

    def longestOfSubString(self, s):
        map = {}
        res = 0
        slidingWidows = []

        for c in s:
            if map.has_key(c) and map[c]:
                delindex = 0
                if c in slidingWidows:
                    delindex = slidingWidows.index(c)
                    slidingWidows.remove(c)
                for i in range(delindex):
                    map[slidingWidows[i]] = False
            else:
                slidingWidows.append(c)
                n = len(slidingWidows)
                if n > res:
                    res = len(slidingWidows)
            map[c] = True

        return res

    def longestPalinrome(self, s):
        # if not s or len(s)==0:
        #     return ""
        res = s[0:1]
        dp = {}
        for i in range(len(s)):
            dp[i] = {}
            for j in range(i, len(s)):
                if j - i == 0:
                    dp[i][j] = True
                elif j - i == 1 and s[i] == s[j]:
                    dp[i][j] = True
                elif j - i == 2 and s[i] == s[j]:
                    dp[i][j] = True
                elif s[i] == s[j] and (
                        (dp.has_key(i) and dp[i].has_key(j) and dp[i][j]) or self.isPalindrome(s[i + 1:j])):
                    dp[i][j] = True
                if dp.has_key(i) and dp[i].has_key(j) and dp[i][j] and j - i + 1 > len(res):
                    res = s[i:j + 1]
        return res

    def maxArea(self, heights):
        leftPos = 0
        rightPos = len(heights) - 1
        max = 0
        while leftPos < rightPos:
            curArea = abs(leftPos - rightPos) * min(heights[leftPos], heights[rightPos])
            if curArea > max:
                max = curArea
            if heights[leftPos] < heights[rightPos]:
                leftPos += 1
            else:
                rightPos -= 1
        return max

    def threeNum(self, nums):
        list = []
        nums.sort()
        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            left = i
            right = len(nums) - 1
            while left < right:
                if left == i:
                    left += 1
                elif right == i:
                    right -= 1
                elif nums[left] + nums[right] + nums[i] == 0:
                    list.append([nums[left], nums[right], nums[i]])
                    while nums[left] == nums[left + 1]:
                        left += 1
                    left += 1
                    while nums[right] == nums[right - 1]:
                        right -= 1
                    right -= 1
                    continue
                elif nums[left] + nums[right] + nums[i] > 0:
                    right -= 1
                else:
                    left += 1
        return list

    def search(self, nums, target):
        if len(nums) <= 0:
            return -1
        left = 0
        right = len(nums) - 1
        while left < right:
            mid = (right - left) // 2 + left
            if nums[mid] == target:
                return mid
            if nums[mid] > nums[left]:
                if nums[left] <= target <= nums[mid]:
                    right = mid
                else:
                    left = mid + 1
            else:
                if nums[mid + 1] <= target < nums[right]:
                    left = mid + 1
                else:
                    right = mid
        return left if nums[left] == target else -1

    def combinationSum(self, candidates, target):
        size = len(candidates)
        if size <= 0:
            return []

        candidates.sort()

        path = []
        res = []
        self._find_path(target, path, res, candidates, 0, size)
        return res

    def _find_path(self, target, path, res, candidates, begin, size):
        if target == 0:
            res.append(copy.deepcopy(path))
        else:
            for i in range(begin, size):
                left_num = target - candidates[i]
                if left_num < 0:
                    break
                path.append(candidates[i])
                self._find_path(left_num, path, res, candidates, i, size)
                path.pop()

    def combinationSum2(self, candidates, target):
        size = len(candidates)
        if size <= 0:
            return []

        candidates.sort()
        path = []
        res = []
        self._find_path2(target, path, res, candidates, 0, size)
        return res

    def _find_path2(self, target, path, res, candidates, begin, size):
        if target == 0:
            res.append(copy.deepcopy(path))
        else:
            for i in range(begin, size):
                left_num = target - candidates[i]
                if left_num < 0:
                    break
                if i > begin and candidates[i] == candidates[i - 1]:
                    continue
                path.append(candidates[i])
                self._find_path2(left_num, path, res, candidates, i + 1, size)
                path.pop()

    def permute(self, numsc):
        res = []

        def _backtrace(nums, pre_list):
            if len(nums) <= 0:
                res.append(pre_list)
            else:
                for i in nums:
                    p_list = copy.deepcopy(pre_list)
                    p_list.append(i)
                    left_nums = copy.deepcopy(nums)
                    left_nums.remove(i)
                    _backtrace(left_nums, p_list)

        _backtrace(numsc, [])
        return res

    def uniquePaths(self, m, n):
        dp = []
        for i in range(m):
            dp.append([])
            for j in range(n):
                dp[i].append(0)

        dp[0][0] = 1
        for i in range(m):
            for j in range(n):
                if i == 0 and j == 0:
                    continue
                first = 0
                sec = 0
                if i > 0:
                    first = dp[i - 1][j]
                if j > 0:
                    sec = dp[i][j - 1]
                dp[i][j] = first + sec

        return dp[m - 1][n - 1]

    def exist(self, board, word):
        m = len(board)
        n = len(board[0])

        def dfs(board, r, c, word, index):
            if index == len(word):
                return True
            if r < 0 or r >= m or c < 0 or c >= n or board[r][c] != word[index]:
                return False
            board[r][c] = "*"
            res = dfs(board, r - 1, c, word, index + 1) or dfs(board, r + 1, c, word, index + 1) or dfs(board, r, c - 1,
                                                                                                        word,
                                                                                                        index + 1) or dfs(
                board, r, c + 1, word, index + 1)
            board[r][c] = word[index]
            return res

        for r in range(m):
            for c in range(n):
                if board[r][c] == word[0]:
                    if dfs(board, r, c, word, 0):
                        return True

    def numDecodins(self, s):
        dp = range(len(s) + 1)
        for i in range(len(s) + 1):
            dp[i] = 0

        dp[0] = 1
        dp[1] = 1 if s[0] != "0" else 0
        for i in range(2, len(s) + 1):
            one = int(s[i - 1:i])
            two = int(s[i - 2:i])
            if two >= 10 and two <= 26:
                dp[i] = dp[i - 2]
            if one >= 1 and one <= 9:
                dp[i] += dp[i - 1]
        return dp[len(dp) - 1]

    def slove(self, board):
        rows = len(board)
        if rows == 0: return []
        cols = len(board[0])

        def mask(board, i, j, rows, cols):
            if i < 0 or i > rows - 1 or j < 0 or j > cols - 1 or board[i][j] != 'O':
                return
            board[i][j] = 'A'
            mask(board, i + 1, j, rows, cols)
            mask(board, i - 1, j, rows, cols)
            mask(board, i, j + 1, rows, cols)
            mask(board, i, j - 1, rows, cols)

        for i in range(rows):
            for j in range(cols):
                if i == 0 or i == rows - 1 or j == 0 or j == cols - 1:
                    mask(board, i, j, rows, cols)

        for i in range(rows):
            for j in range(cols):
                if board[i][j] == 'O':
                    board[i][j] = 'X'
                elif board[i][j] == 'A':
                    board[i][j] = 'O'
            # for

    def partition(self, s):
        def backtrack(s, list, tempList, start):
            sliced = s[start:]
            tempLen = 0
            for str in tempList:
                tempLen += len(str)
            if self.isPalindrome(sliced) and tempLen == len(s):
                list.append(tempList)

            for i in range(len(s)):
                sub = sliced[0:i + 1]
                if self.isPalindrome(sub):
                    tempList.append(sub)
                else:
                    continue
                backtrack(s, list, tempList, start + i + 1)
                tempList.pop()

        list = []
        backtrack(s, list, [], 0)
        return list

    def wordBreak(self, s, wordDict):
        dp = []
        for i in range(len(s) + 1):
            dp.append(False)
        dp[0] = True

        for i in range(len(s) + 1):
            for word in wordDict:
                if len(word) <= i and dp[i - len(word)]:
                    if s[i - len(word):i] == word:
                        dp[i] = True

        return dp[len(s)] or False

    def evalRPN(self, tokens):
        stack = []

        for index in range(len(tokens)):
            token = tokens[index]

            if token.isdigit():
                stack.append(token)
            else:
                a = int(stack.pop())
                b = int(stack.pop())
                if token == "*":
                    stack.append(b * a)
                elif token == "/":
                    stack.append(b / a >> 0)
                elif token == "+":
                    stack.append(b + a)
                elif token == "-":
                    stack.append(b - a)

        return stack.pop()

    def maxProduct(self, nums):
        imin = nums[0]
        imax = nums[0]
        res = nums[0]

        for i in range(1, len(nums)):
            tmp = imin
            imin = min(nums[i], min(nums[i] * imin, nums[i] * imax))
            imax = max(nums[i], max(nums[i] * tmp, nums[i] * imax))
            res = max(res, imax)

        return res

    def numIslands(self, grid):
        def helper(grid, i, j, rows, cols):
            if i < 0 or j < 0 or i > rows - 1 or j > cols or grid[i][j] == '0':
                return

            grid[i][j] = '0'
            helper(grid, i - 1, j, rows, cols)
            helper(grid, i + 1, j, rows, cols)
            helper(grid, i, j - 1, rows, cols)
            helper(grid, i, j + 1, rows, cols)

        res = 0
        rows = len(grid)
        cols = len(grid[0])

        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == '1':
                    helper(grid, i, j, rows, cols)
                    res += 1

        return res

    def minSubArrayLen(self, s, nums):
        num_len = len(nums)
        left = 0
        right = 0
        total = 0
        min_len = num_len + 1

        while (right < num_len):
            total += nums[right]
            right += 1
            while (right < num_len and total < s):
                total += nums[right]
                right += 1
            while left < right and total - nums[left] >= s:
                total -= nums[left]
                left += 1
            if total >= s and min_len > right - left:
                min_len = right - left

        return min_len if min_len <= num_len else 0

    def maximalsSquare(self, matrix):
        dp = []
        rows = len(matrix)
        cols = len(matrix[0])
        imax = 0

        for i in range(rows + 1):
            dp.append([])
            for j in range(cols + 1):
                dp[i].append(0)

        for i in range(1, rows + 1):
            for j in range(1, cols + 1):
                if matrix[i - 1][j - 1] == 1:
                    dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
                    imax = max(imax, dp[i][j])
                else:
                    dp[i][j] = 0

        return imax * imax

    def searchMatrix(self, matrix, target):
        colindex = 0
        rowIndex = len(matrix) - 1
        while rowIndex > 0 and target < matrix[rowIndex][colindex]:
            rowIndex -= 1

        while colindex < len(matrix[0]):
            if target == matrix[rowIndex][colindex]:
                return True
            if target > matrix[rowIndex][colindex]:
                colindex += 1
            elif rowIndex > 0:
                rowIndex -= 1
            else:
                return False
        return False

    def numSquares(self, n):
        if n <= 0:
            return 0

        dp = []
        for i in range(n + 1):
            dp.append(20000000000)
        dp[0] = 0
        for i in range(1, n + 1):
            j = 1
            while j * j <= i:
                dp[i] = min(dp[i], dp[i - j * j] + 1)
                j += 1

        return dp[n]

    def maxProfitPro(self, prices):
        if len(prices) <= 1:
            return 0

        buy = {}
        sell = {}

        buy[0] = -prices[0]
        buy[1] = max(-prices[0], -prices[1])

        sell[0] = 0
        sell[1] = max(0, prices[1] - prices[0])

        for i in range(2, len(prices)):
            buy[i] = max(buy[i - 1], sell[i - 2] - prices[i])
            sell[i] = max(sell[i - 1], buy[i - 1] + prices[i])

        return max(buy[len(prices) - 1], sell[len(prices) - 1], 0)

    def coinChange(self, coins, amount):
        if amount == 0:
            return 0

        dp = []
        for i in range(amount + 1):
            dp.append(200000000)

        dp[0] = 0

        for i in range(1, len(dp)):
            for j in range(len(coins)):
                if i - coins[j] >= 0:
                    dp[i] = min(dp[i], dp[i - coins[j]] + 1)

        return -1 if dp[len(dp) - 1] == 200000000 else dp[len(dp) - 1]

    def increasingTriplet(self, nums):
        if len(nums) < 3:
            return False
        n1 = 200000000
        n2 = 200000000
        for i in range(len(nums)):
            if nums[i] <= n1:
                n1 = nums[i]
            elif nums[i] <= n2:
                n2 = nums[i]
            else:
                return True

        return False

    def canMeasureWater(self, x, y, z):
        if x + y < z: return False
        if z == 0: return False
        if x == 0: return y == z
        if y == 0: return x == z

        def GCD(a, b):
            imin = min(a, b)
            while (imin):
                if a % imin == 0 and b % imin == 0:
                    return imin
                imin -= 1
            return 1

        return z % GCD(x, y) == 0

    def longestPalidromeSubseq(self, s):
        dp = []
        for i in range(len(s)):
            dp.append([])
            for j in range(len(s)):
                dp[i].append(0)
        i = len(s) - 1
        while i >= 0:
            for j in range(i, len(s)):
                if i - j == 0:
                    dp[i][j] = 1
                elif s[i] == s[j]:
                    dp[i][j] = dp[i + 1][j - 1] + 2
                else:
                    dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])
            i -= 1

        print (dp)
        return dp[0][len(s) - 1]


class MyQueue:

    def __init__(self):
        self.stack = []
        self.help_stack = []

    def push(self, x):
        while self.stack:
            self.help_stack.append(self.stack.pop())
        self.help_stack.append(x)
        while self.help_stack:
            self.stack.append(self.help_stack.pop())

    def pop(self):
        return self.stack.pop()

    def peek(self):
        return self.stack[-1]

    def empty(self):
        return not bool(self.stack)


so = Solution()

print (so.isValid("(){}]"))
print (so.isValid("{{[()]}}"))

# print (so.removeDuplicates([1, 1, 2, 3, 4, 5, 6, 6]))

print (so.maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
print (so.maxSubArray1([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
print (so.maxSuArray2([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
print (so.maxSubArray3([-2, 1, -3, 4, -1, 2, 1, -5, 4]))

cc = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

a1 = [1, 2, 3, 0, 0, 00, ]
a2 = [2, 3, 4, 0, 0, 0, 0]

so.merge(a1, 3, a2, 3)

print (a1)

print (so.maxProfit([7, 1, 5, 3, 6, 4]))
print (so.maxMulProfit([7, 1, 5, 3, 6, 4]))

print (so.isPalindrome("a  a"))
print (so.isPalindrome("a e   a"))

print (so.isPalindrome("a c v a"))
print (so.isPalindrome2("a e   a"))

print (so.singleNumber([1, 2, 2, 3, 1]))

print (so.twoSum([2, 7, 11, 15], 9))
print (so.twoSum2([2, 7, 11, 15], 9))

print (so.trailingZeros2(30))
print (so.trailingZeros(30))
print (so.trailingZeros2(25))
print (so.trailingZeros(25))
print (so.jiechen(25))
print (so.jiechen(5))

print (so.majorityElement([1, 1, 1, 3, 3]))

print (bin(so.reverseBits(0b110011001100000000000000111100)))

print (so.hanmingWeight(0b00001110011))

print (so.containsNearByDuplicate([1, 2, 3, 1], 3))

my = MyQueue()
my.push(10)

print (my.pop())
print (so.isUgly(6))
print (so.isUgly(7))
print (so.isUgly(8))

ii = [0, 1, 0, 3, 8, 0]
so.moveZeros(ii)
print (ii)

s = "hahhaha"

s.isdigit()

print (so.intersection([1, 2, 3, 4], [2, 2, 3, 6]))
print (so.intersection2([1, 2, 3, 4], [2, 2, 3, 6]))
print (so.getsum(2, 3))

print (so.longestOfSubString("abcabcbb"))

print (so.longestOfSubString("bbbbb"))

print (so.longestPalinrome("aababaacsdsesa"))

print ("abcdefghj"[0:1 + 1])

print (so.maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]))

print (so.threeNum([-1, 0, 1, 2, -1, -4]))

print (so.search([4, 5, 6, 7, 0, 1, 2], 0))
print (so.search([4, 5, 6, 7, 0, 1, 2], 3))

print (so.combinationSum([2, 3, 6, 7], 7))
print (so.combinationSum([2, 3, 5], 8))

print (so.combinationSum2([10, 1, 2, 7, 6, 1, 5], 8))
print (so.combinationSum2([2, 5, 2, 1, 2], 5))

print ("-------------------------")
print (so.permute([1, 2, 3]))

print (so.uniquePaths(7, 3))

board = []
board.append(['A', 'B', 'C', 'E'])
board.append(['S', 'F', 'C', 'S'])
board.append(['A', 'D', 'E', 'E'])

print (so.exist(board, "ABCCED"))

print (so.numDecodins("226"))
print (so.numDecodins("12"))
print (so.numDecodins("132"))

board1 = []
board1.append(['X', 'X', 'X', 'X'])
board1.append(['X', 'O', 'O', 'X'])
board1.append(['X', 'X', 'O', 'X'])
board1.append(['X', 'O', 'X', 'X'])

so.slove(board1)
print (board1)

# print (so.partition("aab"))

s = "leetcode"
wordDict = ["leet", "code"]
print (so.wordBreak(s, wordDict))
print (so.wordBreak("catsandog", ["cats", "dog", "sand", "and", "cat"]))

s = ["aa", "cc"]
s.append("jajja")
print (s.pop())

print (so.evalRPN(["2", "1", "+", "3", "*"]))

print (so.maxProduct([2, 3, -2, 4]))

grid = []
grid.append(['1', '1', '1', '0', '0'])
grid.append(['1', '0', '0', '0', '0'])
grid.append(['0', '1', '1', '0', '0'])
grid.append(['1', '0', '0', '0', '0'])

print (so.numIslands(grid))

print (so.minSubArrayLen(7, [2, 3, 1, 2, 4, 3]))

matrix = []
matrix.append([1, 1, 1, 1, 1])
matrix.append([1, 0, 1, 1, 0])
matrix.append([0, 1, 1, 0, 1])
matrix.append([1, 0, 1, 1, 1])
print (so.maximalsSquare(matrix))

matrix = []
matrix.append([1, 4, 7, 11, 15])
matrix.append([2, 5, 8, 12, 19])
matrix.append([3, 6, 9, 16, 22])
matrix.append([10, 13, 14, 17, 24])
matrix.append([18, 21, 23, 26, 30])
print (so.searchMatrix(matrix, 5))
print (so.searchMatrix(matrix, 20))

print (so.numSquares(12))

print (so.maxProfitPro([1, 2, 3, 0, 2]))

print ("------")
print (so.coinChange([1, 2, 5, ], 11))

print ("----<<<<<0")
print (so.increasingTriplet([1, 2, 3, 4, 5]))
print (so.increasingTriplet([5, 4, 3, 2]))

print ("-----canMeasureWater")
print (so.canMeasureWater(3, 5, 4))
print (so.canMeasureWater(2, 6, 5))

print("-------longest")
print (so.longestPalidromeSubseq("bbbab"))
